package com.cqs.leetcode.backtrack;


import java.util.LinkedHashMap;
import java.util.Map;

public class WordSearch79 {

    static class Solution {
        private char[][] board = null;
        private char[] word;


        public boolean exist(char[][] board, String word) {
            if (word.length() > board.length * board[0].length) return false;
            this.board = board;
            this.word = word.toCharArray();
            boolean[] usedIndex = new boolean[board.length * board[0].length];
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[0].length; j++) {
                    //exist函数调用结束之后 userIndex所有的元素会还原成全部为false的状态
                    if (exist(i, j, 0, usedIndex)) {
                        return true;
                    }
                }
            }
            return false;
        }

        private boolean exist(int i, int j, final int wordIndex, boolean[] usedIndex) {
            int idx = getIndex(i, j);
//            System.out.println(i + "\t" + j + "\t" + wordIndex + "\t" + idx + "\t" + TestCaseUtils.arrFormat(usedIndex));
            if (idx < 0 || board[i][j] != word[wordIndex] || usedIndex[idx]) return false;
            //终止条件
            if (wordIndex == word.length - 1) return true;
            usedIndex[idx] = true;
            //上下左右方向搜索
            if (exist(i - 1, j, wordIndex + 1, usedIndex)) return true;
            if (exist(i, j + 1, wordIndex + 1, usedIndex)) return true;
            if (exist(i + 1, j, wordIndex + 1, usedIndex)) return true;
            if (exist(i, j - 1, wordIndex + 1, usedIndex)) return true;
            usedIndex[idx] = false;
            return false;
        }

        private int getIndex(int i, int j) {
            if (i < 0 || j < 0 || i >= board.length || j >= board[0].length) return -1;
            return i * board[0].length + j;
        }
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        Map<char[][], String> map = new LinkedHashMap<>();

        map.put(new char[][]{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}}, "ABCCED");
        map.put(new char[][]{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}}, "ABCB");

        map.forEach((k, v) -> {
            System.out.println(solution.exist(k, v));
        });
    }
}
